class Solution {
public:
    int editDistance(string s1, string s2) {
        int n1 = s1.size();
        int n2 = s2.size();
        vector<vector<int>> dp(n2+1, vector<int>(n1+1));
        for (int i = 0; i <= n1; ++i) {
            dp[0][i] = i;
        }
        for (int j = 1; j <= n2; ++j) {
            dp[j][0] = j;
        }
        for (int j = 1; j <= n2; ++j) {
            for (int i = 1; i <= n1; ++i) {
                if (s1[i-1] == s2[j-1]) {
                    dp[j][i] = dp[j-1][i-1];
                } else {
                    dp[j][i] = min(dp[j-1][i-1], min(dp[j][i-1], dp[j-1][i])) + 1;
                }
            }
        }
        return dp[n2][n1];
    }
};